package math;

/**
 * @Description 剑指 Offer II 072. 求平方根
 * @Author Firenut
 * @Date 2023-05-04 17:33
 */
public class T072_mySqrt {
    // 牛顿迭代法: 根据函数 y = x^2 - C,令初始值 x = C
    // 计算x=C处的斜截式方程与x轴交点,然后继续迭代下去
    // 直到前后两点之间的距离小于1e-7,可认为其无限接近于 根号C
    public int mySqrt(int x) {
        if (x == 0) return 0;
        int c = x;
        double x0 = x;
        double x1;
        while (true) {
            x1 = 0.5 * (x0 + c / x0);
            if (x0 - x1 < 1e-7) break;
            x0 = x1;
        }
        return (int) x1;
    }
}
